#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

// 169. 多数元素

// 使用分治方法（Divide and Conquer）
// Time Complexity: O(nlogn)
// Space Complexity: O(logn) for recursive call

class Solution {

public:
    int majorityElement(vector<int> &nums) {
        assert(nums.size() > 0);

        return majorityElement(nums,0, nums.size() - 1);
    }

private:
    int majorityElement(const vector<int>& nums, int left, int right) {
        int len = right - left + 1;
        if(len <= 2) {
            assert(len >= 1);   // 1个元素或者2个元素的时候
            return nums[left];
        }

        int mid = (left +right) / 2;
        cout << "left = "<<left<<",right = "<<right<<",mid = "<< mid <<endl;
        int leftMajority = majorityElement(nums, left, mid);    // 注意这里不是 mid - 1
        int rightMajority = majorityElement(nums, mid+1,right);
        cout << "leftMajority="<<leftMajority<<",rightMajority="<<rightMajority<<endl;
        if(leftMajority == rightMajority)
            return leftMajority;
        // 如果两边的majority不相等，则比较那边出现的次数大
        int leftMajorityCnt = occurance(nums, left, mid, leftMajority);
        int rightMajorityCnt = occurance(nums, mid+1, right, rightMajority);
        assert(leftMajority != rightMajority);
        return leftMajorityCnt > rightMajorityCnt ? leftMajority : rightMajority;
    }
    int occurance(const vector<int>& nums, int l, int r, int target) {
        int cnt = 0;
        for(int i = l; i <= r; i++)
            cnt++;
        return cnt;
    }
};

int main() {
//    vector<int> nums = {3,2,3};
//    cout << Solution().majorityElement(nums) << endl;   // 3

    vector<int> nums = {2,2,1,1,1,2,2};
    cout << Solution().majorityElement(nums) << endl;   // 2
}